TNotes.leetcode

Appearance

⏰0074. 搜索二维矩阵【中等】

0074. 搜索二维矩阵【中等】 ​

1. 🔗 links ​

2. 📝 题目描述 ​

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target，如果 target 在矩阵中，返回 true ；否则，返回 false。

示例 1：

img

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

img

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -10^4 <= matrix[i][j], target <= 10^4

3. 🎯 s.1 - flat ​

javascript
var searchMatrix = function (matrix, target) {
  return matrix.flat().includes(target)
}
  • 将二维数组转换为一维 - Array.prototype.flat() - 将数组拍扁。
js
;[0, 1, 2, [3, 4]].flat() // => [0, 1, 2, 3, 4]
;[0, 1, 2, [[[3, 4]]]].flat(2) // => [0, 1, 2, [3, 4]]
// flat() 参数默认值为 1
  • img

4. 🎯 s.1 - 循环二维数组 ​

javascript
var searchMatrix = function (matrix, target) {
  const rows = matrix.length,
    cols = matrix[0].length
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const item = matrix[r][c]
      if (item === target) return true
    }
  }
  return false
}
  • 两个 for 循环，暴力循环二维数组的每一项。
    • 一旦发现与目标值 target 相等的项，则返回 true，表示在该二维数组 matrix 中找到了目标值。
    • 若找完所有项都没找到与目标值相等的值，则返回 false，表明该二维数组 matrix 中不存在目标值。
  • img

5. 🎯 s.1 - 二分查找 ​

javascript
var searchMatrix = function (matrix, target) {
  const rows = matrix.length,
    cols = matrix[0].length
  let start = 0,
    end = rows * cols - 1
  while (start <= end) {
    const mid = start + ((end - start) >> 1),
      r = parseInt(mid / cols),
      c = mid % cols,
      item = matrix[r][c]
    if (item === target) return true
    else if (item < target) start = mid + 1
    else end = mid - 1
  }
  return false
}
  • 将二维数组视作一维数组来做，并且题目明确该二维数组是有序的。
  • img